#include <iostream>
#include <algorithm>
#include <ctime>
#define ArrSize 100//一亿数据量
using namespace std;

typedef int SplitSortType;//排序时的目标类型
typedef int SplitSortPosType;//表示数组下标的类型

int swapfunc(SplitSortType &a, SplitSortType &b) {
    SplitSortType SwapTemp = a;
    a = b;
    b = SwapTemp;
    return 0;
}

void SplitSort(SplitSortType *TargetArr, SplitSortPosType StartPos, SplitSortPosType EndPos, bool IsFirstNum = true) {
    if (IsFirstNum)//如果这是第一次调用
		EndPos--;//将结尾指针自减1，防止溢出
	if (StartPos + 1 >= EndPos) {//如果数组大小小于等于1
		if (StartPos >= EndPos) {//数组大小为空
			return;//退出递归
		} else {
			if (TargetArr[StartPos] > TargetArr[EndPos]) {//单独进行一次交换操作
				SplitSortType SwapTemp = TargetArr[StartPos];
				TargetArr[StartPos] = TargetArr[EndPos];
				TargetArr[EndPos] = SwapTemp;
			}
			return;//退出
		}
		return;//防止计算失真导致if语句崩掉，再来一次return
	}
	SplitSortPosType LeftPos = StartPos + ((EndPos - StartPos) / 3),//数组的三分之一的位置
                     RightPos = StartPos + (((EndPos - StartPos) / 3) * 2);//数组的三分之二的位置
	(TargetArr[StartPos] > TargetArr[EndPos]) ? swapfunc(TargetArr[StartPos], TargetArr[EndPos]) : SplitSortType();
    (TargetArr[StartPos] > TargetArr[RightPos]) ? swapfunc(TargetArr[StartPos], TargetArr[RightPos]) : SplitSortType();
    (TargetArr[LeftPos] > TargetArr[EndPos]) ? swapfunc(TargetArr[LeftPos], TargetArr[EndPos]) : SplitSortType();
    (TargetArr[StartPos] > TargetArr[LeftPos]) ? swapfunc(TargetArr[StartPos], TargetArr[LeftPos]) : SplitSortType();
    (TargetArr[LeftPos] > TargetArr[RightPos]) ? swapfunc(TargetArr[LeftPos], TargetArr[RightPos]) : SplitSortType();
    (TargetArr[RightPos] > TargetArr[EndPos]) ? swapfunc(TargetArr[RightPos], TargetArr[EndPos]) : SplitSortType();
	SplitSortType LeftPivot = TargetArr[LeftPos], 
                  RightPivot = TargetArr[RightPos];//设置基准数
	SplitSortPosType LessPivot = StartPos;//小于基准的边界
	SplitSortPosType GreaterPivot = EndPos;//大于基准的边界
	SplitSortPosType i = StartPos;//当前元素的索引

	while (i <= GreaterPivot) {
		if (TargetArr[i] < LeftPivot) {//将当前元素交换到小于基准的部分
			SplitSortType SwapTemp = TargetArr[i];
			TargetArr[i] = TargetArr[LessPivot];
			TargetArr[LessPivot] = SwapTemp;
			LessPivot++;
			i++;
		} else if (TargetArr[i] > RightPivot) {//将当前元素交换到大于基准的部分
			SplitSortType SwapTemp = TargetArr[i];
			TargetArr[i] = TargetArr[GreaterPivot];
			TargetArr[GreaterPivot] = SwapTemp;
			GreaterPivot--;
            //i++;
		} else {
			i++;
		}
	}
	//递归地对小于基准和大于基准的部分进行排序
	SplitSort(TargetArr, StartPos, LessPivot - 1, false);//递归的时候因为已经自减完了，因此最后一个参数设为false
    SplitSort(TargetArr, LessPivot, GreaterPivot, false);
	SplitSort(TargetArr, GreaterPivot + 1, EndPos, false);
}

int main(int argc, char *argv[]) {
	int *SortNum = new int[ArrSize];
	cout << "Make Random Nums..." << endl;
	for (int i = 0; i < ArrSize; i++)
		SortNum[i] = rand() % 10000;
	cout << "Random Finish!" << endl << "Start Sort..." << endl;
	cout << endl;
	time_t StartTime = clock();
	SplitSort(SortNum, 0, ArrSize);
	time_t EndTime = clock();
	cout << "Checking Result..." << endl;
	for (int i = 0; i < ArrSize; i++) {//检查一遍递归结果正确性
		if (i + 1 < ArrSize)
			if (SortNum[i] > SortNum[i + 1]) {
				cout << "Error:" << SortNum[i] << " " << SortNum[i + 1] << "  ";
			}
	}
	cout << endl;
	cout << "The Sort Time:" << double(EndTime - StartTime) / CLOCKS_PER_SEC << "s" << endl << "Press Any Key to Exit...";
	delete[] SortNum;
	return 0;
}